﻿#include <iostream>
#include <vector>
#include <string> 
#include <map>
#include <unordered_map>
using namespace std;


////////////////////////////////////////////////////error 90/97
class Solution1 {
public:
    int minOperations(vector<int>& nums, int x)
    {
        int sum1 = 0;
        int sum2 = 0;
        int len = 0;
        int ret = -1;
        int target = 0;
        for (auto e : nums)
        {
            sum1 += e;
        }
        target = sum1 - x;
        int left = 0, right = 0;
        for (right = 0; right < nums.size(); right++)
        {
            sum2 += nums[right];
            while (left < right && sum2 > target)
            {
                sum2 -= nums[left++];
            }

            if (sum2 == target)
            {
                len = max(len, right - left + 1);
                ret = nums.size() - len;
            }
        }

        return ret;
    }
};

int minOperations(vector<int>& nums, int x)
{
    int sum1 = 0;
    int sum2 = 0;
    int len = -1;
    int target = 0;
    for (auto e : nums)
        sum1 += e;
    target = sum1 - x;
    if (target < 0)
        return -1;
    int left = 0, right = 0;
    for (right = 0; right < nums.size(); right++)
    {
        sum2 += nums[right];
        while (sum2 > target)
        {
            sum2 -= nums[left++];
        }

        if (sum2 == target)
        {
            len = max(len, right - left + 1);
        }
    }
    if (len == -1)
        return len;
    else
        return nums.size() - len;
}

//int main()
//{
//
//    vector<int> v{ 8828,9581,49,9818,9974,9869,9991,10000,10000,10000,9999,9993,9904,8819,1231,6309};
//    int ret = minOperations(v, 134365);
//    cout << ret << endl;
//    return 0;
//}



//水果成篮
int totalFruit(vector<int>& fruits) 
{
    int kinds = 0;
    unordered_map<int, int> hash;
    int left=0, right = 0;
    for (right = 0; right < fruits.size(); right++)
    {
        hash[fruits[right]]++;
        while (hash.size() > 2)
        {
            hash[fruits[left]]--;
            if (hash[fruits[left]] == 0)
            {
                hash.erase(fruits[left]);
            }
            left++;
        }

        kinds = max(kinds, right
            - left + 1);

     }
    return kinds;
}

class Solution2
{
public:
    int totalFruit(vector<int>& f)
    {
        int hash[100001] = { 0 }; // 统计窗⼝内出现了多少种⽔果
        int ret = 0;
        for (int left = 0, right = 0, kinds = 0; right < f.size(); right++)
        {
            if (hash[f[right]] == 0) kinds++; // 维护⽔果的种类
            hash[f[right]]++; // 进窗⼝
            while (kinds > 2) // 判断
            {
                // 出窗⼝
                hash[f[left]]--;
                if (hash[f[left]] == 0) kinds--;
                left++;
            }
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};

//int main()
//{
//    vector<int> v{ 1,2,1,2,3,2,3,3};
//    Solution2 r;
//    int ret = r.totalFruit(v);
//    cout << ret << endl;
//    return 0;
//}


//error
//vector<int> findAnagrams(string s, string p)
//{
//    unordered_map<char, int> counthash;
//    for (int i = 0; i < p.size(); i++)
//    {
//        counthash[p[i]]++;
//    }
//    unordered_map<char, int> tmp;
//    int len = p.size();
//    vector<int> ret;
//    for (int left=0,right = 0; right < s.size(); right++)
//    {
//        if (tmp.empty())
//        {
//            for (int i = 0; i < len; i++)
//            {
//                tmp[s[i]]++;
//            }
//            right += len-1;
//        }
//        else
//        {
//
//            tmp.erase(s[static_cast<std::basic_string<char, std::char_traits<char>, std::allocator<char>>::size_type>(left) - 1]);
//            tmp.insert(make_pair(s[right], 1));
//        }
//        if (counthash == tmp)
//        {
//            ret.push_back(left);
//        }
//
//        left++;
//        
//    }
//
//    return ret;
//}

int check(int arr1[], int arr2[])
{
    size_t sz = 26;
    for (int i = 0; i < sz; i++)
    {
        if (arr1[i] != arr2[i])
        {
            return 0;
        }
    }
    return 1;
}
vector<int> findAnagrams(string s, string p)
{
    int hash1[26] = { 0 };
    for (int i = 0; i < p.size(); i++)
    {
        hash1[p[i] - 'a']++;
    }
    int m = p.size();
    int hash2[26] = { 0 };
    vector<int> r;
    for (int left = 0, right = 0;right < s.size(); right++)
    {
        hash2[s[right] - 'a']++;
        if (right - left + 1 > m)
        {
            hash2[s[left++]-'a']--;
        }
        int ret = check(hash1, hash2);
        if (ret)
        {
            r.push_back(left);
        }
    }
    return r;
}

vector<int> findAnagrams(string s, string p)
{
    vector<int> ret;
    int hash1[26] = { 0 }; // 统计字符串 p 中每个字符出现的个数
    for (auto ch : p) hash1[ch - 'a']++;
    int hash2[26] = { 0 }; // 统计窗⼝⾥⾯的每⼀个字符出现的个数
    int m = p.size();
    for (int left = 0, right = 0, count = 0; right < s.size(); right++)
    {
        char in = s[right];
        // 进窗⼝ + 维护 count
        if (++hash2[in - 'a'] <= hash1[in - 'a']) count++;
        if (right - left + 1 > m) // 判断
        {
            char out = s[left++];
            // 出窗⼝ + 维护 count
            if (hash2[out - 'a']-- <= hash1[out - 'a']) count--;
        }
        // 更新结果
        if (count == m) ret.push_back(left);
    }
    return ret;
}

vector<int> findAnagrams(string s, string p)
{
    int hash1[26] = { 0 };
    for (int i = 0; i < p.size(); i++)
    {
        hash1[p[i] - 'a']++;
    }
    int m = p.size();
    int hash2[26] = { 0 };
    vector<int> r;
    for (int left = 0, right = 0,count =0;right < s.size(); right++)
    {
        hash2[s[right] - 'a']++;
        if (hash2[s[right] - 'a'] <= hash1[s[right] - 'a']) count++;

        if (right - left + 1 > m)
        {
            if (hash2[s[left] - 'a'] <= hash1[s[left] - 'a']) count--;

            hash2[s[left++]-'a']--;
        }

        if (count == m)
        {
            r.push_back(left);
        }
    }
    return r;
}

int main()
{
    string s1("cbaebabacd");
    string s2("abc");
    vector<int> ret = findAnagrams(s1,s2);
    for (auto e : ret)
    {
        cout << e <<" " << endl;
    }
    return 0;
}


